অ্যাডভান্সড সর্টিং: Merge Sort, Quick Sort, Heap Sort

অ্যাডভান্সড সর্টিং অ্যালগরিদমগুলো বড় ডেটাসেটকে দ্রুত ও কার্যকরভাবে সাজানোর জন্য ব্যবহৃত হয়। এখানে আমরা Merge Sort, Quick Sort, এবং Heap Sort সম্পর্কে বিস্তারিত আলোচনা করব।

১. Merge Sort

Merge Sort একটি ডিভাইড-অ্যান্ড-কনকার (Divide and Conquer) ভিত্তিক অ্যালগরিদম যা অ্যারেকে দুই ভাগে বিভক্ত করে, তারপর প্রতিটি অংশকে রিকার্সিভভাবে সর্ট করে এবং শেষ পর্যন্ত উভয় অংশকে মিলে একটি সর্টেড অ্যারে তৈরি করে।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: O(n log n) সর্বদা
• স্পেস কমপ্লেক্সিটি: O(n), কারণ অতিরিক্ত মেমোরি প্রয়োজন হয়
• স্থায়িত্ব: স্ট্যাবল, কারণ এটি সমমানের উপাদানের ক্রম ঠিক রাখে

উদাহরণ কোড (Swift):

func mergeSort(arr: [Int]) -> [Int] {
    if arr.count <= 1 { return arr }
    
    let mid = arr.count / 2
    let left = mergeSort(arr: Array(arr[..<mid]))
    let right = mergeSort(arr: Array(arr[mid...]))
    
    return merge(left, right)
}

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var mergedArr = [Int]()
    var i = 0, j = 0
    
    while i < left.count && j < right.count {
        if left[i] < right[j] {
            mergedArr.append(left[i])
            i += 1
        } else {
            mergedArr.append(right[j])
            j += 1
        }
    }
    
    return mergedArr + left[i...] + right[j...]
}

কিভাবে কাজ করে:

1. অ্যারেকে মধ্যবিন্দু থেকে দুই ভাগে বিভক্ত করে।
2. প্রতিটি ভাগকে আলাদাভাবে সর্ট করে।
3. অবশেষে, দুটি সর্ট করা ভাগ মিলে একটি পুরোপুরি সর্টেড অ্যারে তৈরি করে।

২. Quick Sort

Quick Sort আরেকটি ডিভাইড-অ্যান্ড-কনকার অ্যালগরিদম যা পিভট (Pivot) বাছাই করে অ্যারেকে ভাগ করে এবং প্রতিটি অংশকে সর্ট করে। এর প্রধান সুবিধা হলো এটি সাধারণত ইন-প্লেস সর্টিং করে, অর্থাৎ অতিরিক্ত মেমোরি প্রয়োজন হয় না।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: গড়ে O(n log n), তবে খারাপ ক্ষেত্রে O(n^2) হতে পারে (যদি সব সময় খারাপ পিভট বাছাই হয়)
• স্পেস কমপ্লেক্সিটি: O(log n) ইন-প্লেস, অর্থাৎ অতিরিক্ত মেমোরি লাগে না।
• স্থায়িত্ব: আনস্ট্যাবল, কারণ সমমানের উপাদানগুলোর ক্রম পরিবর্তিত হতে পারে

উদাহরণ কোড (Swift):

func quickSort(arr: inout [Int], low: Int, high: Int) {
    if low < high {
        let pivotIndex = partition(&arr, low: low, high: high)
        quickSort(arr: &arr, low: low, high: pivotIndex - 1)
        quickSort(arr: &arr, low: pivotIndex + 1, high: high)
    }
}

func partition(_ arr: inout [Int], low: Int, high: Int) -> Int {
    let pivot = arr[high]
    var i = low
    
    for j in low..<high {
        if arr[j] <= pivot {
            arr.swapAt(i, j)
            i += 1
        }
    }
    arr.swapAt(i, high)
    return i
}

কিভাবে কাজ করে:

1. একটি পিভট এলিমেন্ট নির্বাচন করে।
2. অ্যারের উপাদানগুলোকে পিভটের চারপাশে পুনর্বিন্যাস করে, যাতে পিভটের বামে ছোট উপাদান এবং ডানে বড় উপাদান থাকে।
3. রিকার্সিভভাবে প্রতিটি অংশকে সর্ট করে।

৩. Heap Sort

Heap Sort একটি কমপ্লিট বাইনারি ট্রি ব্যবহার করে সর্টিং করে, যেখানে প্রতিটি নোড তার চাইল্ড নোড থেকে বড় বা ছোট হয়। এটি মূলত ম্যাক্স-হিপ বা মিন-হিপ ব্যবহার করে একটি সর্টেড অ্যারে তৈরি করে।

বৈশিষ্ট্য:

• টাইম কমপ্লেক্সিটি: সর্বদা O(n log n)
• স্পেস কমপ্লেক্সিটি: O(1), কারণ এটি ইন-প্লেস সর্টিং করে
• স্থায়িত্ব: আনস্ট্যাবল, কারণ উপাদানগুলোর ক্রম পরিবর্তিত হতে পারে

উদাহরণ কোড (Swift):

func heapSort(arr: inout [Int]) {
    let n = arr.count
    
    // Build max heap
    for i in stride(from: n / 2 - 1, through: 0, by: -1) {
        heapify(&arr, n, i)
    }
    
    // Extract elements from heap one by one
    for i in stride(from: n - 1, through: 1, by: -1) {
        arr.swapAt(0, i)  // Move current root to end
        heapify(&arr, i, 0)
    }
}

func heapify(_ arr: inout [Int], _ n: Int, _ i: Int) {
    var largest = i
    let left = 2 * i + 1
    let right = 2 * i + 2
    
    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        arr.swapAt(i, largest)
        heapify(&arr, n, largest)
    }
}

কিভাবে কাজ করে:

1. প্রথমে অ্যারেকে একটি ম্যাক্স হিপে রূপান্তরিত করে।
2. তারপর হিপ থেকে এলিমেন্টগুলো সরিয়ে একটি সর্টেড অ্যারে তৈরি করে। প্রতিটি ধাপে সর্বোচ্চ মানের এলিমেন্টটি হিপ থেকে সরানো হয় এবং হিপকে পুনর্গঠিত করা হয়।

উপসংহার

এই তিনটি অ্যাডভান্সড সর্টিং অ্যালগরিদম বিভিন্ন পরিস্থিতিতে উপযোগী:

• Merge Sort: যখন স্থায়িত্ব প্রয়োজন এবং O(n log n) নিশ্চিত দরকার।
• Quick Sort: সাধারণত দ্রুততম, তবে খারাপ ক্ষেত্রে O(n^2) হয়ে যেতে পারে।
• Heap Sort: ইন-প্লেস এবং সর্বদা O(n log n), তবে স্থায়িত্ব নেই।

এগুলো নির্বাচন প্রয়োজনীয়তাভেদে করা হয় এবং প্রতিটি অ্যালগরিদমের নিজস্ব কিছু সুবিধা ও সীমাবদ্ধতা রয়েছে।